Testing hardware, firmware, and software implementations of communication protocols, testing VLSI circuits and testing rule-based expert systems, to name a few, in effective and efficient ways is crucial for the successful operation and maintenance of the end products. During product development, designers would quickly grasp the chance to uncover as many implementation errors as possible thereby eliminating or severely reducing costly correction and maintenance after product release.
Product complexity and informality of the underlying product specification or interface protocol make exhaustive testing, that is, testing every testable aspect of the specified product, impractical or even infeasible without at least some well-guided computer assistance. It has been estimated that testing a communication protocol implementation at the network layer (ISO layer 3) for ISDN services without an efficient technique for minimizing the testing would require at least ten days due to complexity of the services offered. Ad hoc testing of rule-based expert systems is expected to require a minimum of several months time. In all, testing would be conducted in these examples on only a subset of testable aspects for the product at hand. As a result, the testing procedure would admit a number and, perhaps, a seriously large number of implementation errors to exist undetected.
Looking in more detail at the example of a communication protocol, it is understood that protocols are a precise set of rules used to define possible interactions among elements of a complex communication system. To ensure that such system elements communicate reliably when the system is finally implemented, the system protocols as implemented must be tested for conformance to their specification. Typically, a protocol implementation is tested for conformance by applying, by means of an external tester, a sequence of inputs and verifying that the corresponding sequence of outputs is as expected. Testing is further complicated by limited controllability and observability of the protocol implementation by the external tester. These limitations serve, in the first instance, to inhibit the tester from placing the protocol into a predetermined state and, in the second instance, to inhibit direct observation of the state of the protocol implementation. Since even the most simple protocols may admit an astronomically large number of input sequences, protocol testing becomes a combinatorially challenging problem.
To address these concerns, a method for mechanizing the testing process using unique input/output sequences was disclosed in U.S. Pat. No. 4,692,921 issued to A. Dahbura et al. on Sept. 8, 1987 and commonly assigned. The disclosed method is said to tour through and test all edges of a finite state machine. Protocols and VLSI circuits may be modeled as deterministic finite state machines represented as a directed graph. Vertices of the graph correspond to states of the machine and a directed edge of the graph, from one vertex to the same or a different vertex, represents a transition between the two states. According to the patented method, a test for each edge is developed by constructing a three-part test sequence. The first part is a sequence that places the machine at the head state of the edge, that is, at the state which enables the edge to be reached. The second part executes the transition of the edge by supplying the input signal expected by that edge. Traversal of the edge places that machine in the tail state of the edge. Verification that the tail state was indeed reached is accomplished by the third part of the sequence which provides a input/output sequence unique to the tail state. Unique input/output sequences are selected on the basis of minimized length.